package acwing_02;

import java.util.Scanner;

public class _835_Trie字符串统计 {
	static int N = 100010;
	static int son[][];
	static int cnt[];
	static int idx;
	static StringBuilder stb = new StringBuilder();
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		// 并没有某个输入用来控制字符串长度，所以字符串长度有可能是题目最长长度 1e5（10的5次方）
		String str[] = new String[N];
		son = new int[N][26];
		cnt = new int[N];
		
		for(int i = 0 ;i <= n; i++) {
			str[i] = scan.nextLine();
		}
		
		for(int i = 0 ;i <= n; i++) {
			String arr[] = str[i].split(" ");
			if(arr[0].equals("I")) {
				insert(arr[1]);
			}
			if(arr[0].equals("Q")) {
				query(arr[1]);
			}
		}
		
		System.out.print(stb.toString());
		scan.close();
		
	}
	
	public static void insert(String str) {
		// p表示第几层，一开始是在根节点0
		int p = 0;
		for(int i = 0; i < str.length(); i++) {
			// 字母转化为数字作为下标，即该数字对应的是某个字母
			int u = str.charAt(i) - 'a';
			// 如果第p层的边u是0，说明这个点未走过，则赋值++idx
			if(son[p][u] == 0) {
				son[p][u] = ++idx;
			}
			// 将该层的idx值赋值给p
			// 这里需要特别关注idx，它是不断自增的，所以每个不同字符串最终结尾的idx都是不同的
			// 如果是相同的字符串，上面的if就不会去自增idx
			// 如果匹配到相同的字符串，这里p拿到的就是字符串第i个字符的idx
			// 如果匹配到不同的字符串，这里p拿到的就是自增过的idx，也就是新的字符串的idx
			p = son[p][u];
		}
		// 直到循环结束，p拿到的就是最后一个字符的idx
		cnt[p]++;
	}
	
	public static void query(String str) {
		int p = 0;
		for(int i = 0; i < str.length(); i++) {
			int u = str.charAt(i) - 'a';
			// p层的边u如果是0，说明该路径没走过，说明没有匹配字符串，直接跳出
			if(son[p][u] == 0) {
				stb.append("0\n");
				return;
			}
			// 能匹配到则拿其son[p][u]，son中存储了字符的idx，
			// 如果完全匹配到了，就会拿到最后一个字符的idx，通过idx在cnt[]中拿到统计到该字符串的次数
			p = son[p][u];
		}
		// 能到这里说明所有的字符都匹配，说明有该单词，返回该单词位置统计的次数
		stb.append(cnt[p] + "\n");

	}
}
